//------------------------------------------------------------------
//
//	hash tree implementation
//	this is actually a header file
//	to implement the template  class
//
//------------------------------------------------------------------
#include <malloc.h>
#include <string.h>
#include "hashtree.h"

//------------------------------------------------------------------
//	enumerate all the hash tree items
//------------------------------------------------------------------
void	HashTreeItem::Enumerate( void (*fn)( void *pData ) ) const
{
	fn(pData);
	if( branches[0] )	branches[0]->Enumerate(fn);
	if( branches[1] )	branches[1]->Enumerate(fn);
}

//------------------------------------------------------------------
//	StaticHashTree
//	find by hash
//------------------------------------------------------------------
void	*StaticHashTree::FindByHash( HASH byHash ) const
{
	HashTreeItem*	ret;
	u32				shift;

	// search through hash tree to find the correct placement
	ret = m_root;
	for( shift=0;ret;++shift )
	{
		if( ret->hashValue==byHash )
			return ret->pData;
		ret = ret->branches[(byHash>>shift)&1];
	}
	return (ret==null)?null:ret->pData;
}

//------------------------------------------------------------------
//	StaticHashTree
//	set up the static hash tree
//------------------------------------------------------------------
void	StaticHashTree::SetData( u32 nItems, HashTreeItem *pItems )
{
	m_nItems = nItems;
	m_root = pItems;
}


//------------------------------------------------------------------
//	HashTree
//	destructor
//------------------------------------------------------------------
HashTree::~HashTree()
{
	Clear(true);
}

//------------------------------------------------------------------
//	HashTree
//	Remove all the items from the tree
//------------------------------------------------------------------
void	HashTree::Clear( bool freeMemory )
{
	HashTreeItem	*pItem,**ppLast;

	if( freeMemory )
	{
		while( (pItem=m_allocatedItems) )
		{
			m_allocatedItems = pItem->branches[0];
			free(pItem);
		}
		m_freeItems = null;
		m_root = null;
	}
	else if( m_root )
	{
		// remove all items...
		// make the tree into a linear linked list
		ppLast = MakeLinear(m_root,&pItem);

		//	put into free list
		ppLast[0] = m_freeItems;
		m_freeItems = pItem; 

		// show the tree as empty
		m_root = 0;
		m_nItems = 0;
	
	}
}

//------------------------------------------------------------------
//	HashTree
///	recursively add all items from a given node into a linear list
//	returns a pointer to the last element's next pointer
//------------------------------------------------------------------
HashTreeItem **HashTree::MakeLinear( HashTreeItem *pItem, HashTreeItem **ppList )
{
	if( pItem==0 )	return ppList;

	ppList[0] = pItem;
	ppList = &pItem->branches[0];

	ppList = MakeLinear(pItem->branches[0],ppList);
	return MakeLinear(pItem->branches[1],ppList);
}

//------------------------------------------------------------------
//	HashTree
//	staticly populate the free list
//------------------------------------------------------------------
void	HashTree::AddFreeItems( HashTreeItem *pItems, u32 nItems )
{
	u32		i;

	// put all of these items into the free list
	for( i=1;i<nItems;i++ )
		pItems[i-1].branches[0] = &pItems[i];
	pItems[i-1].branches[0] = m_freeItems;
	m_freeItems = pItems;
}
//------------------------------------------------------------------
//	HashTree
//	allocate new items
//------------------------------------------------------------------
void	HashTree::CreateEmptyItems( u32 nItems )
{
	u32				size;
	HashTreeItem	*newItems;

	// allocate one more than we need
	size = (nItems+1)*sizeof(HashTreeItem);
	newItems = (HashTreeItem*)malloc(size);
	memset(newItems,0,size);

	// put a record in the allocated items list
	newItems->branches[0] = m_allocatedItems;
	m_allocatedItems = newItems;

	// put all of these items into the free list
	AddFreeItems(&newItems[1],nItems);
}

//------------------------------------------------------------------
//	HashTree
//	get a free item
//------------------------------------------------------------------
HashTreeItem *HashTree::GetFreeItem()
{
	HashTreeItem	*ret = m_freeItems;

	if( ret==0 )
	{
		CreateEmptyItems(32);
		ret = m_freeItems;
	}
	m_freeItems = ret->branches[0];
	ret->branches[0] = null;
	ret->branches[1] = null;
	return ret;
}

//------------------------------------------------------------------
//	HashTree
//	get the placement for a piece of data
//------------------------------------------------------------------
HashTreeItem** HashTree::GetPlacement( HASH hash )
{
	HashTreeItem**	ret;
	u32				shift;

	// search through hash tree to find the correct placement
	ret = &m_root;
	for( shift=0;ret[0] && ret[0]->hashValue!=hash;++shift )
	{
		ret = &ret[0]->branches[(hash>>shift)&1];
	}
	return ret;
}

//------------------------------------------------------------------
//	HashTree
//	add a piece of data to the hash tree by hash
//------------------------------------------------------------------
bool HashTree::AddByHash( HASH hashValue, void *pData )
{
	HashTreeItem	**ppme;
	HashTreeItem	*newItem;

	// find where it goes
	ppme = GetPlacement(hashValue);
	if( ppme[0]!=0 )	// did a collision occur?
		return false;

	// fill out a new item
	newItem = GetFreeItem();
	newItem->hashValue = hashValue;
	newItem->pData = pData;

	// add to the tree
	ppme[0] = newItem;

	m_nItems++;
	return true;
}

//------------------------------------------------------------------
//	HashTree
//	remove a piece of data to the hash tree by hash
//------------------------------------------------------------------
bool	HashTree::RemoveByHash( HASH hashValue )
{
	HashTreeItem	**ppNext;
	HashTreeItem	*pCurrent;

	// find where it is
	ppNext = GetPlacement(hashValue);
	if( ppNext[0]==0 )	// is it in the tree?
		return false;

	//	1. Start at the node to be removed
	//	2. Choose the left node as the next node if it exists; otherwise choose the right node.
	//	3. If the next node does not exist, move the current node into the free list and finish
	//	4. Copy the next node data and hash into the current node.
	//	5. Move to the next node and go back to step 2
	while( 1 )
	{
		pCurrent = ppNext[0];
		if( pCurrent->branches[0] )
			ppNext = &pCurrent->branches[0];
		else if( pCurrent->branches[1] )
			ppNext = &pCurrent->branches[1];
		else
			break;

		pCurrent->hashValue = ppNext[0]->hashValue;
		pCurrent->pData     = ppNext[0]->pData;
	}

	// remove item pCurrent, pointed to by ppNext[0]
	// and place in the free list
	ppNext[0] = 0;
	pCurrent->branches[0] = m_freeItems;
	m_freeItems = pCurrent;

	m_nItems--;

	return true;
}
